In order to apply optimization algorithms to design optimization problems it is essential to find ways to describe the shape of a design by a set of parameter which can be modified by the optimization algorithm. A well known method is for example to define a spline line, for two dimensional designs or a spline surface for three dimensional designs, which describe the surface of the object which is to be optimized. In this case the parameter which are modified by the optimization algorithms are the control and knot points, in the case of NURBS (non rational B-splines) additionally the weights of the control points. Another way of representing a given design is to define a transformation function which transforms the space in which a basic design is given. In this case a variation of a shape can be realized by modifying parameter of a transformation function. These methods can be summarized under the term of Constrained Deformation.
Constrained Deformation
The principle of constrained deformation is formulated by Borrel and Bechman in P. Borrel and D. Bechmann, Deformation of n-dimensional Objects, International Journal of Computational Geometry Applications, 1(4):427-453, 1991 which is incorporated by reference herein in its entirety. They developed a general deformation scheme in which the deformation is defined by an arbitrary number of user-specified point displacement constraints. The deformation method from Borrel and Bechmann, which is illustrated in FIG. 1, is based on the following principle: the original and deformed space Rn are two projections of a higher dimensional space Rm. The deformation is thus defined by the composition of a function f: Rn→Rm that transforms the points of the original space Rn into points of Rm with a projection T from Rm back onto Rn. The projection matrix is computed so as to achieve given displacements (called constraints) of given points (called constraints points) of the original space.
Mathematically stated, the deformation function d, which expresses the transformation on any point of Rn, is expressed as the composition of a function f: Rn→Rm (m>n) with a linear transformation T: Rm→Rn. If UεRn and M the corresponding matrix of T, results in:d(U)=Mf(U).
Different functions f produces different types of deformation, global or local for example. The concrete deformation depends only on the matrix M. The corresponding transformation T selects an “appropriate” deformation from the set of potential ones. The greater m in contrast to n the larger the range of possible deformations.
Generally, this model encapsulates a large family of possible deformations: for example, linear space transformations are obtained if f is linear, or FFD are obtained if f is a tensor product Bernstein polynomial and if M is built with displacement vectors of control points.
Once f and m are specified the choice of an appropriate M and consequently the transformation of arbitrary points UεRn is carried out in three steps with the help of the nc constraint points Vi:
1. Select the desired displacement of the nc constraint points Vi, iε[1, nc]. These points essentially establish the degrees of freedom for a design optimization.
2. The projection matrix M is obtained by solving n systems of nc equations, each with m unknowns constituting one row of M. This system in turn is derived from the n×nc equations:d(Vi)=Mf(Vi)∀iε[1,nc]
Unfortunately, this system of equations is not uniquely solvable in any case, which constitutes the main drawback of the technique described here. Three situations may be distinguished: (a) If m is greater than nc and all f(Vi) vectors are linearly independent there exists an infinity of solutions. Choosing one M by the user fixes the deformation. Several ways to do so were discussed by Borrel and Bechmann, (b) If m=nc only one solution M exists, (c) Otherwise no deformation can be found satisfying the constraints. In this case a best approximate solution is used.
3. The displacement of any point U is computed by d(U)=Mf(U).
Due to the fact that the re-transformations M only depends on the constraint points Vi, the deformation of an initial object U (set of points Ul) can be carried out very efficiently. The values f(Ul) need to be computed only once and can then be used for several deformations defined by several sets of constraints. Consequently, design optimization requires the re-computation of the values of f(Vi) only for the constraints added, deleted or changed, and not for the object points Ul.
As already pointed out, the selection process of M is technically demanding and requires user interaction. Additionally, the shape of the deformation is not strongly correlated with the constraints which makes the technique non-intuitive.
In order to circumvent these deficits, Borrel and Rappoport simplified the general constraint deformation concept, now termed Simplified Constraint Deformation short “Scodef” in P. Borrel and A. Rappoport, Simple Constrained Deformations for Geometric Modeling and Interactive Design, ACM Transactions on Graphics, 13(2):137-155, April 1994 which is incorporated by reference herein in its entirety. The central idea of the Scodef approach is the unification of the re-transformation M and therefore the simplification of the whole process. This is achieved by the choice of f as a tensor product of B-spline basis functions each centered at a constraint point where each point influences the deformation process. Additionally, for each of the nc constraint points a radius is introduced which affects the scope of each B-spline, i.e., each basis function falls to zero beyond the radius of the corresponding constraint point. Thus the different radii may be used for a fine-tuning of the deformation process. Consequently, a Scodef deformation can be viewed as the deformation obtained by creating an arbitrary number of possible overlapping B-spline-shaped “bumps” over the space. The location and height of a bump are defined by a constraint and its width by the constraints radius of influence.
For a design optimization using ESs the constraints and/or the displacements of the constraints constitute the free parameters which may be modified with the help of ES-standard genetic operators. In the case of the simple constraint deformation, the radii associated with the nc constraint points Vi may be used as additional design parameters. As a result from that, three groups of design parameters are available which make the technique very flexible in the number of design parameters. In the best case only four constraint points are necessary for the deformation of a 3D object. Additionally, due to the underlying system of nc equations, triples of constraint points, their displacements and radii can easily be added or deleted without influencing other design parameters. Of course, such an adaptation process can change the structure of the transformation matrix M and therefore the resulting design. This is in contrast to e.g., B-splines or NURBS where curve or surface preserving addition operators exist which in contrast force the recalculation of control points.
Free Form Deformation (FFD)
Although developed earlier, the Free Form Deformation (FFD) approach (see FIG. 2) is a special case of the constraint deformation approach described above. The FFD approach is described in T. W. Sederberg and S. R. Parry, Free-Form Deformation of Solid Geometric Models, Computer Graphics, 20(4):151-160, August 1986, which is incorporated by reference herein in its entirety.
This is true if the transformation function f is a tensor product of Bernstein polynomials (or B-spline basis functions in the case of the simplified constraint deformation) and if M is built with displacement vectors of control points. Very similar to constraint deformation, FFD focuses on the formulation of a more general interactive shape editing concept. Sederberg and Parry (cited above) considered the precise specification of modifications of curves or surfaces built with Bézier, B-splines and NURBS as too laborious in most situations. Even a perceptually simple change may require adjustment of many control points, see S. Gibson and B. Mirtich, A Survey of Deformable Modeling in Computer Graphics, Tech. Report No. TR-97-19, Mitsubishi Electric Research Lab., Cambridge, November 1997, which is incorporated by reference herein in its entirety.
Sederberg and Parry generalized the approach in Barr (A. H. Barr, Global and Local Deformation of Solid Primitives, Computer Graphics, 18(3):21-30, 1984 which is incorporated by reference herein in its entirety) on regular deformations (i.e., mappings R3 to R2) of solids by embedding an object in a lattice of grid points of some standard geometry such as a cube or cylinder. Manipulating nodes of the grid induces deformations on the space inside the grid with the help of trivariate tensor product Bernstein polynomial. These deformations transform the underlying graphics primitives that form the object. Sederberg and Parry gave a good physical analogy for FFD. Consider a parallelepiped of clear, flexible plastic in which is embedded an object, or several objects, which is to be deformed. The object is imagined to also be flexible, so that it deforms analog with the plastic that surrounds it.
As already pointed out, the first step of the FFD is the fixation of the local coordinate system S, T, U of the enclosing parallelepiped region. With the help of some basic linear algebra, each point X in the parallelepiped may be expressed in the new coordinate system such thatX=X0+sS+tT+uU. 
Since the idea of FFD is that the deformation of the enclosing volume induces deformations on the space inside the volume, the next step is the formulation of a grid of control points Pijk on the parallelepiped. The l grid points in S direction, m points in T direction, and n points in U direction allow for the formulation of the deformed enclosing volume with the help of trivariate tensor product Bernstein polynomials whose control points are the grid points. The deformation of the control points which essentially build the free parameters for a potential design optimization is simply specified by moving the Pijk from their undisplaced lattice positions. The deformed position Xffd of an arbitrary point X is found by first computing its (s, t, u) coordinates in the local coordinate system and then evaluating the vector valued trivariate Bernstein polynomial:
      X    ffd    =            ∑              i        =        0            l        ⁢                  (                                            l                                                          i                                      )            ⁢                        (                      1            -            s                    )                          l          -          i                    ⁢              s        i            ⁢              {                  (                                    ∑                              j                =                0                            m                        ⁢                                          (                                                                            m                                                                                                  j                                                                      )                            ⁢                                                (                                      1                    -                    t                                    )                                                  m                  -                                                            j                      t                                        ⁢                    i                                                              ⁢                              {                                                      ∑                                          k                      =                      0                                        n                                    ⁢                                                            (                                                                                                    k                                                                                                                                n                                                                                              )                                        ⁢                                                                  (                                                  1                          -                          u                                                )                                                                    k                        -                                                                              n                            u                                                    ⁢                          k                                                                                      ⁢                                          P                      ijk                                                                      }                                              }                    where Xffd is a vector containing the Cartesian coordinates of the displaced point, and where each Pijk is a vector containing the Cartesian coordinates of the control points. For deformation techniques a shape modification tool which is independent of the underlying geometric representation is of primary interest.Extended Free Form Deformation (EFFD)
To improve the basic free form deformation concepts which have been introduced by Sederberg et al. with respect to a higher degree of flexibility Coquillart developed a method called Extended Free Form Deformation in S. Coquillart, Free-Form Deformation: A Sculpturing Tool for 3D Geometric Modeling, Computer Graphics, 24(4):187-196, August 1990, which is incorporated by reference herein in its entirety. This method allows the use of arbitrary control volumes in contrast to the restrictive requirement of parallelepiped volumes of control points in standard free form deformation. It mainly falls into three steps which are described briefly as follows, see FIG. 3
At first a lattice of control points has to be constructed which encloses either the whole object or a part of the object which is targeted for being modified. In a second step the geometry coordinates have to be transferred into the spline coordinate system, which is also called “freezing.” By freezing object coordinates the u, v and w coordinates of the geometry in spline parameter space are calculated. This is usually done by Newton approximation which promises to be the fastest approach but it can also be done by similar gradient based methods or even by evolutionary optimization. After the u, v and w coordinates have been calculated successfully the deformations can be applied by moving the control points to the desired positions. The x, y and z coordinates of the surface or solid can be calculated by retransforming the object points from the spline coordinate system to the original used coordinate system. Therefore the B-spline equations have to be solved using the new spatial coordinates of the control points. This method is also valid if the geometry model equals a solid or is defined by parametric or implicit equations.
EFFDs are quite effective for creating impressions, reliefs and other fairly simple deformations that might otherwise be difficult to achieve with FFDs. However, the user must know the general shape of the deformation before starting to model, and the interface is still a direct representation of the underlying mathematics.
More generally, although the movement of control points gives an indication of the resulting deformation, some shapes are not intuitive in form. Complex deformation operations often require a large number of control points to deform.
Direct Manipulation of Freeform Deformations (DFFD)
In view of these problems, a direct approach to freeform deformations has been introduced by Hsu et. al. (Direct Manipulation of Free-Form Deformations, Computer Graphics, 26, 2. July 1992). The essential idea is that the user selects (with some sort of pointer) a point of an object and then moves the pointer to a location where that object point should be. Then, the necessary alteration to the control points of the FFD spline that will induce this change is automatically computed. In general, this problem is under-determined; Hsu et. al. (cf. above) use a least squares approach to select a particular alteration.
This approach is problematic insofar, as the desired direct manipulation of the free form may not be realizable with the current grid of control points, but only with a grid representation that is optimized with respect to its own structure. Such a structure optimization cannot be realized using least square methods.
The problem of an ill structured control volume, using direct manipulation of object points and an application of least squares methods is especially crucial if one wants to prevent loops in the design and invalid surfaces. If the alteration of control points is calculated in a least square sense, the problem often occurs that the order of control points changes which leads to invalid surfaces or volumes.